package cn.z2huo.algorithm.sort.swapSort.quickSort;

import java.util.Random;

/**
 * 快速排序优化，随机选取基准
 * 20年写的
 * 作者： 张一卓
 * 时间： 2020/1/13 15:43
 */
public class QuickSorting2 {
    Random random = new Random();

    public void sort(int[] array, int left, int right) {
        if (array == null) {
            return;
        }
        if (left >= right) {
            return;
        }
        int low = left, high = right;
//        int centerPosition = 3;
        int centerPosition = random.nextInt(right-left+1) + left;
        int centerValue = array[centerPosition];
        while (low < high) {
            // 从序列末端寻找比 centerValue 小的元素
            while (array[high] >= centerValue && low < high) {
                high--;
            }
            // 从序列前端寻找比 centerValue 大的元素
            while (array[low] <= centerValue && low < high) {
                low++;
            }
            // 交换上面找到的两个元素的位置
            if (low < high) {
                int temp = array[high];
                array[high] = array[low];
                array[low] = temp;
            }
        }
        // 当low和high重合后，将 centerPosition 位置的元素值和 重合位置的元素值位置交换
        array[centerPosition] = array[low];
        array[low] = centerValue;

        centerPosition = low;

        sort(array, left, centerPosition-1);
        sort(array, centerPosition + 1, right);

//        if (high-centerPosition > centerPosition-low) {
//            sort(array, left, low-1);
//            sort(array, low + 1, right);
//        }else {
//            sort(array, low + 1, right);
//            sort(array, left, low-1);
//        }
    }
}
